package hoja7;

/**
 * Código de: cs.williams.edu/~morgan/code/RedBlack/RedBlack.java
   Red black tree with a java.Map like interface.  Insert, contains, and get are O(log n)
   worst case time. It is possible to write a constant space, linear
   time iterator for this tree that produces the elements in sorted order.
   
   <p>
   Based on Okasaki, Alternatives to Two Classic Data Structures, SIGCSE 2005

   <P>Morgan McGuire
   <br>morgan@cs.williams.edu
*/
public class RedBlack implements WordSet {

    /**
     *
     * @param wordObject
     */
    @Override
    public void add(Word wordObject) {
        root = root.add(wordObject);
        root.color = Color.BLACK;
    }

    /**
     *
     * @param word
     * @return (null if not found)
     */
    @Override
    public Word get(Word word) {
        Node n = root.getNode(word);
        if (n != null) {
            return n.word;
        } else {
            return null;
        }
    }

    /** Node labels. */
    private enum Color {RED, BLACK};

    /** Value returned from a comparator */
    private static final int LESS    = -1;

    /** Value returned from a comparator */
    private static final int EQUAL   =  0;

    /** Value returned from a comparator */
    private static final int GREATER = +1;
    
    /** NULL when the tree is empty */
    private Node root;

    /** All leaf nodes are black empty nodes that share this one instance. */
    final private Node EMPTY = new Empty();

    public RedBlack() {
        root = EMPTY;
    }
    
    public boolean contains(Word word) {
        return root.getNode(word) != null;
    }

    private class Node {
        public Word    word;
        
        public Color  color;
        public Node   left;
        public Node   right;
        
        /** Used by Empty */
        protected Node() {
            assert EMPTY == null;
        }

        /** Nodes always begin red */
        public Node(Word k) {
            word   = k;
            color = Color.RED;
            left  = EMPTY;
            right = EMPTY;
        }
        
        private boolean isRed() {
            return color == Color.RED;
        }

        public Node add(Word k) {
            switch (k.compareTo(word)) {
            case LESS:
                left = left.add(k);
                break;

            case GREATER:
                right = right.add(k);
                break;

            case EQUAL:
                // word is already in the tree; replace the value
                word = k;
                return this;  
            }
        
        
            // Check for two red nodes in a row: Red child and red grandchild
            if (left.isRed() && left.left.isRed()) {

                //       z           y
                //      / \         / \
                //     y   D  ==>  /   \
                //    / \         x     z
                //   x   C       / \   / \
                //  / \         A   B C   D
                // A   B
                return balance(left.left, left, this,              // x,y,z
                               left.left.right, left.right);       // B,C

            } else if (left.isRed() && left.right.isRed()) {

                //       z           y
                //      / \         / \
                //     x   D  ==>  /   \
                //    / \         x     z
                //   A   y       / \   / \
                //      / \     A   B C   D
                //     B   C
                return balance(left, left.right, this,             // x,y,z
                               left.right.left, left.right.right); // B,C
                
            } else if (right.isRed() && right.left.isRed()) {

                //     x             y
                //    / \           / \
                //   A   z    ==>  /   \
                //      / \       x     z
                //     y   D     / \   / \
                //    / \       A   B C   D
                //   B   C
                return balance(this, right.left, right,            // x,y,z
                               right.left.left, right.left.right); // B,C
                
            } else if (right.isRed() && right.right.isRed()) {
                //   x               y
                //  / \             / \
                // A   y      ==>  /   \
                //    / \         x     z
                //   B   z       / \   / \
                //      / \     A   B C   D
                //     C   D
                return balance(this, right, right.right,           // x,y,z
                               right.left, right.right.left);      // B,C
            }

            return this;
        }


        /** Returns the node for this word, or null. */
        public Node getNode(Word k) {
            switch (k.compareTo(word)) {
            case LESS:
                return left.getNode(k);

            case GREATER:
                return right.getNode(k);

            default: // EQUAL
                return this;
            }
        }

    }

    /** The empty node used at leaves */
    private class Empty extends Node {

        public Empty() {
            color = Color.BLACK;
            assert EMPTY == null : "Should only make one empty node instance!";
        }

        /** Always make a new node, since this one is empty */
        public Node add(Word k) {
            return new Node(k);
        }

        public Node getNode(Word word) {
            return null;
        }
    }

    /**
      Rearrange/recolor the tree as

      <pre>
             y      <== red
            / \
           /   \
          x     z   <== both black
         / \   / \
        A   B C   D
      </pre> 
      Note: A and D are not passed in because already in the right place
    */
    private Node balance(Node x, Node y, Node z, Node B, Node C) {
        
        x.right = B;
        y.left  = x;
        y.right = z;
        z.left  = C;
        x.color = Color.BLACK;
        y.color = Color.RED;
        z.color = Color.BLACK;
        return y;
    }

    
    

}
